package leetcode_1_200;

import java.util.Arrays;

public class LeeCode_167 {
    public static void main(String[] args) {
        int[] ints = twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println(Arrays.toString(ints));
    }
    private static int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for (int i = 0; i < n; i++) {
            if (i > 0 && numbers[i] == numbers[i - 1])
                continue;
            int index = findNum(numbers, i + 1, n - 1, target - numbers[i]);
            if (index != -1)
                return new int[]{i + 1, index + 1};
        }
        return null;
    }
    private static int findNum(int[] numbers, int l, int r, int goal){
        while (l < r){
            int m = l + (r - l) / 2;
            if (numbers[m] < goal){
                l = m + 1;
            }else if (numbers[m] > goal){
                r = m - 1;
            }else {
                return m;
            }
        }
        if (numbers[l] == goal)
            return l;
        if (numbers[r] == goal)
            return r;
        return -1;
    }
}
